package leetcode_101_120;

import utils.TreeNode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class buildTree_105 {

    /**
     * 给定两个整数数组，请构造二叉树并返回其根节点。
     * preorder 和 inorder 均 无重复 元素
     * @param preorder 二叉树的先序遍历
     * @param inorder 同一棵树的中序遍历
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        /**
         * 思路是通过遍历前序数组，可以确定中序数组中不同元素的位置
         * 利用递归确定每一层的根节点
         */
        TreeNode root=new TreeNode();
        //function(root,preorder,inorder);
        function2(root,preorder,inorder,new int[]{0,preorder.length-1},new int[]{0,preorder.length-1});
        return root;
    }

    /**
     * 递归构建
     * 7ms,11%，有点拉
     * 可能是数组的截取太费时间
     * @param root 当前根节点
     * @param preorder 此时处理的二叉树的先序遍历
     * @param inorder 中序遍历
     */
    void function(TreeNode root,int[] preorder, int[] inorder){
        //根节点肯定是先序数组的第一个元素
        root.val=preorder[0];
        if(preorder.length==1)
            return;
        //找到当前左子树包含的所有元素
        int count=0; //左子树元素的个数
        for(int i=0;i<inorder.length;i++){      //找到该树的根节点在中序遍历下的对应位置
            if(inorder[i]==preorder[0]){
                count=i;
                break;
            }
        }
        //例 preorder =[3,9,20,15,7]       inorder = [9,3,15,20,7]
        int []newPreorder_left=Arrays.copyOfRange(preorder,1,count+1);     //左子树的先序数组 [9]
        int []newInorder_left=Arrays.copyOfRange(inorder,0,count); //左子树的中序数组 [9]

        if (newPreorder_left.length != 0) {
            root.left = new TreeNode();
            function(root.left, newPreorder_left, newInorder_left); //处理左子树
        }

        int []newPreorder_right=Arrays.copyOfRange(preorder,count+1,preorder.length); //右子树的先序数组  [20,15,7]
        int []newInorder_tight=Arrays.copyOfRange(inorder,count+1,preorder.length); //右子树的中序数组 [15,20,7]

        if (newPreorder_right.length != 0) {
            root.right = new TreeNode();
            function(root.right, newPreorder_right, newInorder_tight); //处理右子树
        }
    }


    /**
     * 尝试改进，想法取消数组的截取，通过算法得出每一层需要的左右子树的区间
     * 优化到了4ms
     * @param p_index 当前子树的先序遍历范围区间在原区间的左右位置
     * @param i_index 当前子树的中序遍历范围区间的在原区间的左右位置
     */
    void function2(TreeNode root,int[] preorder, int[] inorder,int[] p_index,int i_index[]){
        //根节点肯定是先序数组的第一个元素
        root.val=preorder[p_index[0]];
        if(p_index[0]==p_index[1])
            return;
        //找到当前左子树包含的所有元素
        int count=0; //左子树元素的个数
        for(int i=i_index[0];i<=i_index[1];i++){      //找到该树的根节点在中序遍历下的对应位置
            if(inorder[i]==preorder[p_index[0]]){
                count=i-i_index[0];
                break;
            }

        }
        //例 preorder =[3,9,20,15,7]    [0,4]   inorder = [9,3,15,20,7]  [0,4]
        if (count != 0) { //存在左子树
            int []newP_index_left={p_index[0]+1,p_index[0]+count}; //左子树新的先序区间范围 [9]   [0,0]
            int []newI_index_left= {i_index[0],i_index[0]+count-1};  //左子树新的中序区间范围 [9]  [0,0]
            root.left = new TreeNode();
            function2(root.left, preorder, inorder,newP_index_left,newI_index_left); //处理左子树
        }
        if (count != i_index[1] - i_index[0]) {     //存在右子树
            int[] newP_index_right = {p_index[0] + count + 1, p_index[1]}; //右子树新的先序区间范围  [20,15,7]  [2,4]
            int[] newI_index_right = {i_index[0] + count + 1, i_index[1]};    //右子树新的中序区间范围  [15,20,7]  [2,4]

            root.right = new TreeNode();
            function2(root.right, preorder, inorder, newP_index_right, newI_index_right); //处理右子树
        }
    }


    /**
     * 1ms
     * 使用哈希表来帮助我们快速地定位根节点。
     * 对于哈希映射中的每个键值对，键表示一个元素（节点的值），值表示其在中序遍历中的出现位置
     * 思路大差不差
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree2(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
    private Map<Integer, Integer> indexMap;

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return null;
        }
        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);

        // 先把根节点建立出来
        TreeNode root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }
}
